package com.bichengcao.googlecodejam.practiceproblems;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;

public class AlwaysTurnLeft {

	static int N;

	public static void main(String[] args) throws IOException {
		Input[] inputs = parseInput("src/com/bichengcao/googlecodejam/practiceproblems/B-large-practice.in");
		Output[] outputs = process(inputs);
		writeOutput("src/com/bichengcao/googlecodejam/practiceproblems/AlwaysTurnLeft.out", outputs);
	}

	static class Input {

		String entranceToExit;
		String exitToEntrance;
	}

	static class Output {

		int R, C;
		int[][] maze;
	}

	private static Input[] parseInput(String filename) throws IOException {
		BufferedReader in = new BufferedReader(new FileReader(filename));
		N = Integer.parseInt(in.readLine());
		Input[] array = new Input[N];

		for (int i = 0; i < N; i++) {
			Input input = array[i] = new Input();
			String line = in.readLine();
			String[] splits = line.split(" ");
			input.entranceToExit = splits[0];
			input.exitToEntrance = splits[1];
		}

		in.close();
		return array;
	}

	private static Output[] process(Input[] inputs) {
		Output[] outputs = new Output[N];
		for (int i = 0; i < N; i++) {
			outputs[i] = process(inputs[i]);
		}
		return outputs;
	}

	private static Output process(Input input) {
		Output output = new Output();

		// Calculate the boundaries and entry point
		int[][] directions = { { 0, 1 }, { -1, 0 }, { 0, -1 }, { 1, 0 } };
		int[] mask = {2, 4, 1, 8};
		int left = 0, right = 0, bottom = 0, x = 0, y = -1, d = 0;
		
		// Navigate from entrance to exit
		for (int i = 0; i < input.entranceToExit.length() - 1; i++) {
			char c = input.entranceToExit.charAt(i);
			switch (c) {
			case 'W':
				x += directions[d][0];
				y += directions[d][1];
				if (x < left) {
					left = x;
				}
				if (x > right) {
					right = x;
				}
				if (y > bottom) {
					bottom = y;
				}
				break;
			case 'R':
				d = (d + 1) % 4;
				break;
			case 'L':
				d = (d + 3) % 4;
				break;
			}
		}
		
		// Navigate from exit to entrance
		d = (d + 2) % 4;
		for (int i = 1; i < input.exitToEntrance.length() - 1; i++) {
			char c = input.exitToEntrance.charAt(i);
			switch (c) {
			case 'W':
				x += directions[d][0];
				y += directions[d][1];
				if (x < left) {
					left = x;
				}
				if (x > right) {
					right = x;
				}
				if (y > bottom) {
					bottom = y;
				}
				break;
			case 'R':
				d = (d + 1) % 4;
				break;
			case 'L':
				d = (d + 3) % 4;
				break;
			}
		}
		
		output.R = bottom + 1;
		output.C = right - left + 1;
		output.maze = new int[right - left + 1][bottom + 1];
		
		// Navigate through the maze to calculate each unit
		// Navigate from entrance to exit
		x = 0 - left;
		y = 0;
		d = 0;
		output.maze[x][y] |= 1;
		for (int i = 1; i < input.entranceToExit.length() - 1; i++) {
			char c = input.entranceToExit.charAt(i);
			switch (c) {
			case 'W':
				output.maze[x][y] |= mask[d];
				x += directions[d][0];
				y += directions[d][1];
				output.maze[x][y] |= mask[(d + 2) % 4];
				break;
			case 'R':
				d = (d + 1) % 4;
				break;
			case 'L':
				d = (d + 3) % 4;
				break;
			}
		}
		
		// Navigate from exit to entrance
		output.maze[x][y] |= mask[d];
		d = (d + 2) % 4;
		for (int i = 1; i < input.exitToEntrance.length() - 1; i++) {
			char c = input.exitToEntrance.charAt(i);
			switch (c) {
			case 'W':
				output.maze[x][y] |= mask[d];
				x += directions[d][0];
				y += directions[d][1];
				output.maze[x][y] |= mask[(d + 2) % 4];
				break;
			case 'R':
				d = (d + 1) % 4;
				break;
			case 'L':
				d = (d + 3) % 4;
				break;
			}
		}

		return output;
	}

	private static void writeOutput(String filename, Output[] outputs) throws IOException {
		PrintWriter out = new PrintWriter(new FileWriter(filename));
		for (int i = 0; i < N; i++) {
			out.println("Case #" + (i + 1) + ":");
			for (int j = 0; j < outputs[i].R; j++) {
				for (int k = 0; k < outputs[i].C; k++) {
					out.print(Integer.toHexString(outputs[i].maze[k][j]));
				}
				out.println();
			}
		}
		out.close();
	}

}
